package com.example.interview.algorithm;

import java.util.Arrays;

/**
 * 插入排序
 *
 * @author gaobing
 * @Description: TODO
 * @date 2018年9月29日 下午4:35:38
 * 排序算法中最基本的三种算法（简单选择，冒泡，插入），这三种排序算法的时间复杂度均为O(n2)
 * 简单插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n);在最坏情况下，时间复杂度依然为O(n2)。
 * 但是在数组元素随机排列的情况下，插入排序还是要优于上面两种排序的。
 */
public class Test00charupaixu {

    /**
     * 交换数组元素
     *
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int[] arr, int a, int b) {
        arr[a] = arr[a] + arr[b];
        arr[b] = arr[a] - arr[b];
        arr[a] = arr[a] - arr[b];
    }

    /**
     * 插入排序
     *
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                swap(arr, j, j - 1);
                j--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 8, 9, 4, 2, 1, 7, 5, 3};
        System.out.println(Arrays.toString(arr));
        //引用传递
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));

        //值传递，基本数据类型，包装类型，string
//		String old="1";
//		valueTransfer(old);
//        System.out.println("old: "+old);
    }

    public static void valueTransfer(String old) {
        old = old + "1";
        System.out.println("new: " + old);
    }
}
